{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[True, True, False]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def containsNearbyAlmostDuplicate(nums, k, t):\n",
    "    if t < 0:\n",
    "        return False\n",
    "\n",
    "    # Using a dictionary to maintain a window of size k\n",
    "    window = {}\n",
    "    for i in range(len(nums)):\n",
    "        # Check the bucket for the current number\n",
    "        bucket = nums[i] // (t + 1)\n",
    "        for offset in (-1, 0, 1):\n",
    "            neighbor_bucket = bucket + offset\n",
    "            if neighbor_bucket in window and abs(window[neighbor_bucket] - nums[i]) <= t:\n",
    "                return True\n",
    "\n",
    "        # Add the current number to the bucket\n",
    "        window[bucket] = nums[i]\n",
    "        \n",
    "        # Remove the element which is out of the window\n",
    "        if i >= k:\n",
    "            del window[nums[i - k] // (t + 1)]\n",
    "\n",
    "    return False\n",
    "\n",
    "# Testing the function with the provided examples\n",
    "test_cases = [([1, 2, 3, 1], 3, 0), ([1, 0, 1, 1], 1, 2), ([1, 5, 9, 1, 5, 9], 2, 3)]\n",
    "results = [containsNearbyAlmostDuplicate(nums, k, t) for nums, k, t in test_cases]\n",
    "results\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "修改后"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "10-29 华为面试算法题目\n",
    "管理员需要整理所有货箱，要求如下:\n",
    "将若干 位置连续的货箱堆起，从左至右整理成三堆，每一堆至少有一个货箱;三堆货箱重量满足条件:左边一堆货箱重量<=中间一堆货箱重量<=右边一堆货箱重量。请返回管理员共有多少种满足要求的整理方案;如果无可行方案，返回0。注意:答案需要以1e9+7(1000000007)为底取余，如:计算初始结果为：1000000008，则取余后返回1。\n",
    "示例 1:\n",
    "输入:boxes =[1,1,2,1,4]\n",
    "输出:5\n",
    "解释:有五种整理方法:\n",
    "整理成[1,1,7]，7=boxes[2]+boxes[3]+ boxes[4]=2+1+4，由右侧 3 个货箱堆成一堆;\n",
    "整理成 [1,3,5];\n",
    "整理成[1,4,4];\n",
    "整理成 [2,2,5];\n",
    "整理成 [2,3,4]。\n",
    "限制:\n",
    "3 <= boxes.length <= 10^6\n",
    "1<= boxes[i]<=10^6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MOD = 1000000007\n",
    "\n",
    "def waysToPartitionBoxes(boxes):\n",
    "    n = len(boxes)\n",
    "    prefix_sum = [0] * (n + 1)\n",
    "    \n",
    "    # 计算前缀和\n",
    "    for i in range(n):\n",
    "        prefix_sum[i + 1] = prefix_sum[i] + boxes[i]\n",
    "\n",
    "    total_sum = prefix_sum[-1]\n",
    "    result = 0\n",
    "\n",
    "    # 遍历中间堆的起点位置\n",
    "    for mid_start in range(1, n - 1):\n",
    "        left_sum = prefix_sum[mid_start]\n",
    "        \n",
    "        # 遍历右边的起点位置，确保 left_sum <= middle_sum <= right_sum\n",
    "        for right_start in range(mid_start + 1, n):\n",
    "            middle_sum = prefix_sum[right_start] - left_sum\n",
    "            right_sum = total_sum - prefix_sum[right_start]\n",
    "            \n",
    "            if left_sum <= middle_sum <= right_sum:\n",
    "                result = (result + 1) % MOD\n",
    "\n",
    "    return result\n",
    "\n",
    "# 测试用例\n",
    "boxes = [1, 1, 2, 1, 4]\n",
    "waysToPartitionBoxes(boxes)  # Expected output: 5"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "rag",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.19"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
